package Exercise;

/**
 * Description：
 * Author: zhangc
 * Date：2017/8/29 22:34
 */
public class BinarySearchExercise {

//    public static <T extends Comparable<? super T>> int binarySearch(T[] arr, int low, int high, T key) {
//        if (low > high)
//            return -1;
//        int mid = (low + high) >> 1;
//        if (arr[ mid ].equals(key))
//            return mid;
//        else if (arr[ mid ].compareTo(key) < 0)
//            return binarySearch(arr, mid + 1, high, key);
//        else
//            return binarySearch(arr, low, mid - 1, key);
//    }

    public static <T extends Comparable<? super T>> int binarySearchNo(T[] arr, int low, int high, T key) {
        if (low > high)
            return -1;
        int mid;
        while (low < high) {
            mid = (low + high) >> 1;
            if (arr[ mid ].equals(key))
                return mid;
            else if (arr[ mid ].compareTo(key) < 0)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -1;
    }


    public static void main(String[] args) {
        Integer[] ints = {1, 2, 4, 6, 7, 8, 9, 33};
        System.out.println(binarySearchNo(ints, 0, ints.length - 1, 28));
    }

}
